/**
 * 399. 除法求值
 * https://leetcode-cn.com/problems/evaluate-division/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number} value
 * @param {boolean} isDivide
 * @constructor
 */
function Next(value, isDivide = false) {
  this.value = value;
  this.isDivide = isDivide;
}

/**
 * @param {Map<string, { name: string, nexts: Map<string, Next> }>} nodes
 * @param {string} from
 * @param {string} to
 * @param {Set<string>} searched
 * @param {Map<string, Map<string, Next>>} caches
 * @return {Next}
 */
function searchRelations(nodes, from, to, searched, caches) {
  let cache = caches.get(from);
  if (!cache) {
    cache = new Map();
    caches.set(from, cache);
  }
  if (cache.has(to)) {
    return cache.get(to);
  }
  if (searched.has(from) || !nodes.has(from)) {
    cache.set(to, null);
    return null;
  }
  searched.add(from);
  const node = nodes.get(from);
  const keys = Array.from(node.nexts.keys());
  let key;
  for (let i = 0; i < keys.length; i += 1) {
    key = keys[i];
    if (key === to) {
      const relation = node.nexts.get(key);
      cache.set(to, relation);
      return relation;
    }
    const relationTo = searchRelations(nodes, key, to, searched, caches);
    if (relationTo) {
      const relationFrom = node.nexts.get(key);
      const newRelation = new Next(0);
      if (relationTo.isDivide && relationFrom.isDivide) {
        newRelation.value = relationTo.value * relationFrom.value;
        newRelation.isDivide = true;
      } else if (relationTo.isDivide) {
        newRelation.value = relationFrom.value / relationTo.value;
        newRelation.isDivide = false;
      } else if (relationFrom.isDivide) {
        newRelation.value = relationTo.value / relationFrom.value;
        newRelation.isDivide = false;
      } else {
        newRelation.value = relationTo.value * relationFrom.value;
        newRelation.isDivide = false;
      }
      cache.set(to, newRelation);
      return newRelation;
    }
  }
  cache.set(to, null);
  return null;
}

/**
 * @param {Map<string, { name: string, nexts: Map<string, Next> }>} nodes
 * @param {string} name
 * @return {{ name: string, nexts: Map<string, Next> }}
 */
function findNode(nodes, name) {
  let node = nodes.get(name);
  if (node) {
    return node;
  }
  node = {
    name,
    nexts: new Map(),
  };
  nodes.set(name, node);
  return node;
}

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
function calcEquation(equations, values, queries) {
  const nodes = new Map();
  for (let i = 0; i < equations.length; i += 1) {
    const equation = equations[i];
    const node0 = findNode(nodes, equation[0]);
    const node1 = findNode(nodes, equation[1]);
    node0.nexts.set(equation[1], new Next(values[i]));
    node1.nexts.set(equation[0], new Next(values[i], true));
  }
  const caches = new Map();
  const result = new Array(queries.length).fill(-1);
  let relation;
  for (let i = 0; i < queries.length; i += 1) {
    const query = queries[i];
    relation = searchRelations(nodes, query[0], query[1], new Set(), caches);
    if (relation) {
      if (relation.isDivide) {
        result[i] = 1 / relation.value;
      } else {
        result[i] = relation.value;
      }
    } else {
      result[i] = -1;
    }
  }
  return result;
}

console.log(displayBaseArray(calcEquation(
  [['a', 'b'], ['b', 'c']],
  [2.0, 3.0],
  [['a', 'c'], ['b', 'a'], ['a', 'e'], ['a', 'a'], ['x', 'x']],
)) === '[6,0.5,-1,1,-1]');
console.log(displayBaseArray(calcEquation(
  [['a', 'b'], ['b', 'c'], ['bc', 'cd']],
  [1.5, 2.5, 5.0],
  [['a', 'c'], ['c', 'b'], ['bc', 'cd'], ['cd', 'bc']],
)) === '[3.75,0.4,5,0.2]');
console.log(displayBaseArray(calcEquation(
  [['a', 'b']],
  [0.5],
  [['a', 'b'], ['b', 'a'], ['a', 'c'], ['x', 'y']],
)) === '[0.5,2,-1,-1]');
console.log(displayBaseArray(calcEquation(
  [['x1', 'x2'], ['x2', 'x3'], ['x1', 'x4'], ['x2', 'x5']],
  [3.0, 0.5, 3.4, 5.6],
  [['x2', 'x4'], ['x1', 'x5'], ['x1', 'x3'], ['x5', 'x5'], ['x5', 'x1'], ['x3', 'x4'], ['x4', 'x3'], ['x6', 'x6'], ['x0', 'x0']],
)) === '[1.1333333333333333,16.799999999999997,1.5,1,0.059523809523809534,2.2666666666666666,0.4411764705882353,-1,-1]');
